# codding = utf-8
"""
# 妖怪和和尚过河问题
# 三个和尚在河的左岸,三个妖怪在河的右岸,有一条限乘2只的船,
# 在任何时候,如果一边的和尚比妖怪少,妖怪就要把和尚吃掉
# 怎样过河,和尚不会被吃掉
"""

# 将左岸定义为A
# 右岸为B
# 二元组(和尚数,妖怪数)表示岸上的状态
# 初始A:(3,0),B:(0,3),要求最后为A:(0,3),B:(3,0)
# 乘船定义为AB之间的向量
# state(left_monk,left_monster,right_monk,right_monster)
# initstate = (3, 0, 0, 3)

import os
import logging

logpath = 'debug.log'
if logpath is not None and logpath != '':
    if not os.path.exists(logpath):
        with open(logpath, "w") as f:
            f.close()
    logging.basicConfig(level=logging.DEBUG,
                        format='%(asctime)s %(filename)s[line:%(lineno)d] %(levelname)s %(message)s',
                        datefmt='%a, %d %b %Y %H:%M:%S',
                        filename=logpath,
                        filemode='w')


class Shipping:
    """
    passenger:(monkcount,monstercount)
    direction:'AB' or 'B2A'
    """

    def __init__(self, direction, passenger: tuple):
        self.direction = direction
        self.passengerchange = passenger


Shipping('NOT_TAKE_OFF', (0, 0, 0, 0))
actions = [
    Shipping('A2B', (-2, 0, 2, 0)),
    Shipping('A2B', (-1, 0, 1, 0)),
    Shipping('A2B', (-1, -1, 1, 1)),
    Shipping('A2B', (0, -1, 0, 1)),
    Shipping('A2B', (0, -2, 0, 2)),
    Shipping('B2A', (2, 0, -2, 0)),
    Shipping('B2A', (1, 0, -1, 0)),
    Shipping('B2A', (1, 1, -1, -1)),
    Shipping('B2A', (0, 1, 0, -1)),
    Shipping('B2A', (0, 2, 0, -2))
]


def tuppleadd(t1: tuple, t2: tuple):
    assert len(t1) == len(t2) == 4
    return t1[0] + t2[0], t1[1] + t2[1], t1[2] + t2[2], t1[3] + t2[3]


def getoppsitepos(pos: str):
    return 'right' if pos == 'left'else 'left'


def ship2(state, postion, shipmethod: Shipping):
    logging.debug("-" * 20)
    logging.debug('before ship:%s,position:%s' % (state, postion))
    logging.debug('ship method:%s,%s' % (shipmethod.direction, shipmethod.passengerchange))
    tmpstate = tuppleadd(state, shipmethod.passengerchange)
    if isshipleagal(tmpstate):
        postion = getoppsitepos(postion)
        state = tmpstate
    else:
        logging.error('>>>>>>  illegal shipmethod')
        pass
    logging.debug('after ship:%s,position:%s' % (state, postion))
    return state, postion


def isshipleagal(tmpstate: tuple):
    if tmpstate[0] > 3 or tmpstate[0] < 0 or tmpstate[1] < 0 or tmpstate[1] > 3 or tmpstate[2] > 3 or tmpstate[
        2] < 0 or tmpstate[3] < 0 or tmpstate[3] > 3 or (tmpstate[0] != 0 and tmpstate[0] < tmpstate[1]) or (
                    tmpstate[2] != 0 and tmpstate[2] < tmpstate[3]):
        return False
    return True


# _visitedstate = []


def shipmonkfirst(state, boat_position, visithistory=None, actionhistory=None):
    logging.debug('state=%s,pos=%s' % (str(state), boat_position))
    if visithistory is None:
        visithistory = []
    if state in visithistory[1:]:
        logging.debug('visited state')
        return
    if actionhistory is None:
        actionhistory = []
    visithistory.append(state)
    tmpvisithistory = visithistory.copy()
    tmpactionhistory = actionhistory.copy()
    logging.debug('history:' + str(visithistory))
    if state == (0, 3, 3, 0):
        print('OK', state)
        print('visithistory:', visithistory)
        print('actionhistory:', actionhistory)
        return

    # if len(history) - len(set(history)) > 2:
    #     return
    for shipmethod in actions:
        tmpstate, tmpboat_position = ship2(state, boat_position, shipmethod)
        if tmpstate != state and tmpboat_position != boat_position:
            actionhistory.append('%s-%s' % (shipmethod.direction, shipmethod.passengerchange))
            shipmonkfirst(tmpstate, tmpboat_position, visithistory, actionhistory)
        visithistory = tmpvisithistory.copy()
        actionhistory = tmpactionhistory.copy()


if __name__ == '__main__':
    # 无论船在哪边,都可以通过不下船来变更船的位置,所以结果为一个方向的结果的两倍
    initstate = (3, 0, 0, 3)
    shipmonkfirst(initstate, boat_position='right')
